/LMAR=0/XLINE=3/FONT#0=BASL30/FONT#1=BASB30/FONT#3=BASI30/FONT#4=BDR40/FONT#5=NGR25/FONT#6=NGR20/FONT#7=SUP/FONT#8=SUB





␈↓ ↓H␈↓␈↓ ∧C␈↓∧␈↓&Maximally-Divisible Numbers␈↓)αβ␈↓





␈↓ ↓H␈↓␈↓ ∧␈↓∧Mathematical Concepts Developed by␈↓

␈↓ ↓H␈↓␈↓ ε∂D. Lenat
␈↓ ↓H␈↓␈↓ ε∂R. Davis
␈↓ ↓H␈↓␈↓ βcand the "␈↓βAutomated Mathematician␈↓" computer program




␈↓ ↓H␈↓␈↓∧␈↓&A Meaningful Question␈↓)αβ␈↓

␈↓ ↓H␈↓We␈αbegin␈αby␈αasking␈αthe␈αquestion,␈α"What␈αis␈αthe␈α␈↓βconverse␈↓␈αconcept␈αto␈αprime␈αnumbers?"␈α If␈αwe␈αde≡ne
␈↓ ↓H␈↓"primeness"␈α
to␈α
mean␈α
that␈α
a␈α∞natural␈α
number␈α
has␈α
as␈α
few␈α∞divisors␈α
as␈α
possible␈α
(namely,␈α
just␈α∞two␈α
of
␈↓ ↓H␈↓them:␈α∞1␈α∞and␈α∞itself),␈α
then␈α∞the␈α∞converse␈α∞kind␈α
of␈α∞number␈α∞would␈α∞be␈α
one␈α∞which␈α∞had␈α∞an␈α
abnormally
␈↓ ↓H␈↓␈↓βlarge␈↓ number of divisors.

␈↓ ↓H␈↓One could consider the following set of maximally-divisible numbers:
␈↓ ↓H␈↓␈↓¬M = {xεN␈↓#
+␈↓# | (∀y<x) ( d(y) < d(x) ) }␈↓

␈↓ ↓H␈↓In␈α∂words,␈α∂this␈α∂says␈α∂that␈α∂M␈α∂is␈α∂the␈α∞set␈α∂of␈α∂all␈α∂positive␈α∂integers␈α∂satisfying␈α∂the␈α∂property␈α∂that␈α∞every
␈↓ ↓H␈↓smaller␈αnumber␈αhas␈αfewer␈αdivisors.␈α That␈αis,␈αwe␈αthrow␈αinto␈αthe␈αset␈αM␈αa␈αnumber␈αx␈αif␈α(and␈αonly␈αif)
␈↓ ↓H␈↓it␈αhas␈αmore␈αdivisors␈α
than␈αany␈αsmaller␈αnumber.␈α
 So␈α1␈αgets␈αthrown␈α
in␈α(the␈αsmallest␈αnumber␈α
with␈α1
␈↓ ↓H␈↓divisor),␈α2␈α(having␈α2␈αdivisors),␈α4␈α
(3␈αdivisors,␈αnamely␈α1,␈α2,␈αand␈α
4),␈α6␈α(4␈αdivisors),␈α12␈α(6␈αdivisors),␈α
etc.
␈↓ ↓H␈↓Another␈α
way␈αto␈α
specify␈α
M␈αis␈α
as␈α
the␈αset␈α
containing␈α(for␈α
all␈α
n)␈αthe␈α
smallest␈α
number␈αhaving␈α
at␈αleast␈α
n
␈↓ ↓H␈↓divisors.␈α Notice␈αthat␈αwe␈αare␈α␈↓βnot␈↓␈αgoing␈αto␈αinclude␈α"the␈αsmallest␈αnumber␈αwith␈α␈↓βprecisely␈↓␈α
5␈αdivisors",
␈↓ ↓H␈↓since this number (2␈↓#
4␈↓# = 16) is bigger than 12 (which has 6 divisors).

␈↓ ↓H␈↓One␈αof␈αthe␈α
questions␈αat␈αthe␈αheart␈α
of␈αour␈αstudy␈αis␈α
"Given␈αd,␈αwhat␈αis␈α
the␈αsmallest␈αnumber␈α
with␈αat
␈↓ ↓H␈↓least d divisors?"

␈↓ ↓H␈↓How␈α⊃can␈α⊃we␈α∩even␈α⊃start␈α⊃on␈α∩this␈α⊃question?␈α⊃The␈α∩most␈α⊃powerful␈α⊃tool␈α∩we␈α⊃have␈α⊃is␈α∩the␈α⊃following
␈↓ ↓H␈↓combinatorially-proved theorem:
␈↓ ↓H␈↓␈↓∧(T1)␈↓  If we write n as 2␈↓#
a␈↓#␈↓#
␈↓ε␈↓#
1␈↓␈↓#
␈↓#3␈↓#
a␈↓#␈↓#
␈↓ε␈↓#
2␈↓␈↓#
...␈↓#p␈↓#vk␈↓#␈↓#
a␈↓#␈↓#
␈↓ε␈↓#
k␈↓␈↓#
␈↓#, then d(n) = (a␈↓#v1␈↓#+1)(a␈↓#v2␈↓#+1)...(a␈↓#v␈↓ε␈↓#vk␈↓␈↓#v␈↓#+1).

␈↓ ↓H␈↓Our␈αcentral␈αquestion␈αcould␈αbe␈αanswered␈αif␈αwe␈αcould␈αsomehow␈αinvert␈αthis␈αformula␈αinto␈αone␈αwhich
␈↓ ↓H␈↓expressed␈αn␈αas␈αa␈αfunction␈αof␈αd,␈αand␈αthen␈αfound␈αthe␈αminima␈αof␈αthat␈αfunction␈αn(d).␈α Coupled␈αwith
␈↓ ↓H␈↓the␈α⊂knowledge␈α⊂that␈α⊂each␈α⊂number␈α⊂can␈α⊃be␈α⊂factored␈α⊂uniquely␈α⊂into␈α⊂prime␈α⊂factors,␈α⊂T1␈α⊃provides␈α⊂a
␈↓ ↓H␈↓closed-form␈α
way␈α
of␈α
manipulating␈α
d(n).␈α That␈α
is,␈α
n␈α
is␈α
really␈αa␈α
function␈α
of␈α
the␈α
sequence␈αof␈α
exponents
␈↓ ↓H␈↓when␈α⊃written␈α⊃as␈α∩2␈↓#
a␈↓#␈↓π1␈↓3␈↓#
a␈↓#␈↓π2␈↓...,␈α⊃so␈α⊃we␈α⊃can␈α∩consider␈α⊃n␈α⊃=␈α∩n(a␈↓#v1␈↓#,␈α⊃a␈↓#v2␈↓#,...).␈α⊃ Then␈α⊃T1␈α∩is␈α⊃really␈α⊃a␈α∩way␈α⊃of
␈↓ ↓H␈↓expressing d(n) = d(a␈↓#v1␈↓#, a␈↓#v2␈↓#,...).
␈↓ ↓H␈↓␈↓εDouglas B. Lenat␈↓␈↓ ∧s␈↓β␈↓&Automated Mathematician␈↓)αβ␈↓ results␈↓ λ9␈↓εMaximally-Divisible Numbers      page   2␈↓


␈↓ ↓H␈↓␈↓∧␈↓&Special Case: n = 2␈↓#
a␈↓#3␈↓#
b␈↓#␈↓)αβ␈↓

␈↓ ↓H␈↓Let's␈αconsider␈αa␈α
special␈αcase.␈αWe'll␈α
restrict␈αour␈αattention␈αto␈α
numbers␈αn␈αwhich␈α
are␈αof␈αthe␈αform␈α
2␈↓#
a␈↓#3␈↓#
b␈↓#.
␈↓ ↓H␈↓So␈α
T1␈α
says␈α
that␈α
d(n)=(a+1)(b+1).␈α
 Consider␈α
≡xing␈α
d,␈αand␈α
asking␈α
how␈α
n␈α
varies␈α
with␈α
a␈α
and␈αb.␈α
 Notice
␈↓ ↓H␈↓that␈α∃we␈α∃are␈α∃now␈α⊗saying␈α∃that␈α∃(a+1)(b+1)=d=constant.␈α∃ So␈α⊗we␈α∃can␈α∃say␈α∃that␈α⊗(b+1)=d/(a+1),␈α∃so
␈↓ ↓H␈↓b=(d/(a+1))-1.␈α
 So␈α
our␈α
number␈α
n␈α
is␈α
really␈α2␈↓πa␈↓3␈↓π[(d/(a+1))-1]␈↓.␈α
 Aha!␈α
This␈α
is␈α
an␈α
expression␈α
for␈α
n␈αsimply␈α
as
␈↓ ↓H␈↓a␈αfunction␈αof␈αa.␈α We␈αcan␈αuse␈αcalculus␈αto␈α≡nd␈αthe␈αminima␈αof␈αthis␈αfunction.␈αThat␈αwill␈αcorrespond␈αto
␈↓ ↓H␈↓the optimal exponent a, from which we can compute the optimal b.
␈↓ ↓H␈↓␈↓βd␈↓n/␈↓βd␈↓a  =  2␈↓#
a␈↓#(3␈↓#
b␈↓#(-d/(a+1)␈↓#
2␈↓#)log(3)) + 3␈↓#
(d/(a+1))-1␈↓#(2␈↓#
a␈↓#log(2))
␈↓ ↓H␈↓    = [(a+1)log(2)  -  (b+1)log(3)](n/(a+1)).

␈↓ ↓H␈↓This is zero when (a+1)log(2) = (b+1)log(3).

␈↓ ↓H␈↓So we have two equations now:
␈↓ ↓H␈↓(a+1) = (b+1)log(3)/log(2)
␈↓ ↓H␈↓(a+1) = d/(b+1)

␈↓ ↓H␈↓Together␈αthey␈αsay␈αthat␈α(b+1)log(3)/log(2)␈α =␈α d/(b+1),␈αfrom␈αwhich␈αwe␈αderive␈α(b+1)␈↓#
2␈↓#␈α=␈αlog(2)d/log(3).
␈↓ ↓H␈↓Substituting this back in, we also get that (a+1)␈↓#
2␈↓# = log(3)d/log(2).

␈↓ ↓H␈↓If␈α:real-valued␈α:exponents␈α:were␈α:allowed,␈α:our␈α:optimal␈α:n(d)␈α:would␈α:be
␈↓ ↓H␈↓␈↓∧2␈↓␈↓#
SQRT␈↓#␈↓π[log(3)d/log(2)]␈↓␈↓∧3␈↓␈↓#
SQRT␈↓#␈↓π[log(2)d/log(3)]␈↓.

␈↓ ↓H␈↓Three␈α
observations␈αwe␈α
can␈αmake␈α
from␈αintuition␈α
--␈α
and␈αjustify␈α
from␈αreality␈α
--␈αare␈α
(i)␈α
this␈αoptimal
␈↓ ↓H␈↓real␈αvalue␈αis␈αbetter␈αthan␈α(i.e.,␈α␈↓¬≤␈↓)␈αany␈αintegral␈αn␈α(divisible␈αonly␈αby␈α2␈αand␈α3)␈αwith␈αat␈αleast␈αd␈αdivisors,
␈↓ ↓H␈↓(ii)␈α∞the␈α∞ideal␈α∞n␈α∞is␈α∞very␈α∞close␈α∞to␈α∞the␈α∞best␈α∞such␈α∞integral␈α∞n,␈α∞(iii)␈α∞the␈α∞best␈α∞such␈α∞integral␈α∞n␈α∞will␈α∞have
␈↓ ↓H␈↓exponents a and b which are close to our theoretical real-valued "ideal" a and b.

␈↓ ↓H␈↓For␈α
example,␈α
if␈αwe␈α
choose␈α
to␈α
ask␈αfor␈α
a␈α
number␈α
with␈αat␈α
least␈α
8␈α
divisors,␈αour␈α
theoretical␈α
values␈αfor␈α
a
␈↓ ↓H␈↓and␈αb␈αare␈αabout␈α2.6␈αand␈α1.2;␈αthe␈αideal␈αn␈αis␈αthen␈αabout␈α23.␈αIn␈αactuality,␈αthe␈α≡rst␈αnumber␈αwith␈α8␈αor
␈↓ ↓H␈↓more␈αdivisors␈α
is␈α24,␈α
and␈αit␈α
is␈αfactored␈α
into␈α2␈↓π3␈↓3␈↓π1␈↓␈α
(i.e.,␈αthe␈α
best␈αintegral␈α
values␈αfor␈α
a␈αand␈α
b␈αare␈α3␈α
and
␈↓ ↓H␈↓1, respectively).

␈↓ ↓H␈↓␈↓∧␈↓&Special Case: n = 2␈↓#
a␈↓#3␈↓#
b␈↓#5␈↓#
c␈↓#␈↓)αβ␈↓

␈↓ ↓H␈↓Let's␈α∞consider␈α∞a␈α∞second␈α∞special␈α∂case.␈α∞We'll␈α∞restrict␈α∞our␈α∞attention␈α∂to␈α∞numbers␈α∞n␈α∞which␈α∞are␈α∂of␈α∞the
␈↓ ↓H␈↓form␈α∞2␈↓#
a␈↓#3␈↓#
b␈↓#5␈↓#
c␈↓#.␈α∞So␈α∞T1␈α
says␈α∞that␈α∞d(n)=(a+1)(b+1)(c+1).␈α∞ Consider␈α∞≡xing␈α
d,␈α∞and␈α∞asking␈α∞how␈α∞n␈α
varies
␈↓ ↓H␈↓with␈α
a,␈α
b,␈α
and␈α
c.␈α
 Notice␈α
that␈α
we␈α
are␈α
now␈α
saying␈α
that␈α
(a+1)(b+1)(c+1)=d=constant.␈α
 So␈α
we␈α
can␈α
say
␈↓ ↓H␈↓that (c+1)=d/(a+1)(b+1), so c=(d/(a+1)(b+1))-1.  So our number n is really 2␈↓πa␈↓3␈↓πb␈↓5␈↓π[(d/(a+1)(b+1))-1]␈↓.

␈↓ ↓H␈↓Viewing c as a function of a and b, we can compute the di≥erential
␈↓ ↓H␈↓␈↓βd␈↓c = ␈↓βd␈↓(d/(a+1)(b+1))
␈↓ ↓H␈↓ =  d [␈↓βd␈↓(1/(a+1)(b+1))]
␈↓ ↓H␈↓ = (d)[(1/(a+1))(-1/(b+1)␈↓#
2␈↓#)␈↓βd␈↓b + (1/(b+1))(-1/(a+1)␈↓#
2␈↓#)␈↓βd␈↓a]
␈↓ ↓H␈↓ = (-(c+1)/(b+1))␈↓βd␈↓b + (-(c+1)/(a+1))␈↓βd␈↓a
␈↓ ↓H␈↓␈↓εDouglas B. Lenat␈↓␈↓ ∧s␈↓β␈↓&Automated Mathematician␈↓)αβ␈↓ results␈↓ λ9␈↓εMaximally-Divisible Numbers      page   3␈↓


␈↓ ↓H␈↓We␈α
want␈α∞to␈α
minimize␈α
this␈α∞function␈α
n=n(a,b).␈α
It␈α∞will␈α
turn␈α
out␈α∞to␈α
be␈α
easier␈α∞to␈α
≡nd␈α
the␈α∞minima␈α
of
␈↓ ↓H␈↓log(n),␈α∩viewed␈α∩as␈α∩a␈α⊃function␈α∩of␈α∩a␈α∩and␈α∩b.␈α⊃ Now␈α∩log(n)␈α∩=␈α∩log(2)a␈α⊃+␈α∩log(3)b␈α∩+␈α∩log(5)c.␈α∩ So␈α⊃the
␈↓ ↓H␈↓di≥erential␈α
␈↓βd␈↓n␈α=␈α
log(2)␈↓βd␈↓a␈α+␈α
log(3)␈↓βd␈↓b␈α+␈α
log(5)␈↓βd␈↓c.␈α Substituting␈α
in␈αthe␈α
value␈αwe␈α
obtained␈αfor␈α
␈↓βd␈↓c,␈αwe
␈↓ ↓H␈↓get
␈↓ ↓H␈↓␈↓βd␈↓n = log(2)␈↓βd␈↓a + log(3)␈↓βd␈↓b + log(5)[(-(c+1)/(b+1))␈↓βd␈↓b + (-(c+1)/(a+1))␈↓βd␈↓a]
␈↓ ↓H␈↓= [log(2)-(c+1)log(5)/(a+1)]␈↓βd␈↓a + [log(3)-(c+1)log(5)/(b+1)]␈↓βd␈↓b

␈↓ ↓H␈↓One␈αnice␈α
way␈αto␈α
make␈αthis␈αidentically␈α
zero␈αis␈α
if␈αthe␈α
coe≠cients␈αof␈α␈↓βd␈↓a␈α
and␈α␈↓βd␈↓b␈α
become␈αzero.␈αThat␈α
is,
␈↓ ↓H␈↓n␈α∂will␈α∂have␈α∞minima␈α∂when␈α∂both␈α∂log(2)␈α∞=␈α∂(c+1)log(5)/(a+1)␈α∂and␈α∞log(3)␈α∂=␈α∂(c+1)log(5)/(b+1)␈α∂are␈α∞true.
␈↓ ↓H␈↓That is, when (a+1)log(2) = (b+1)log(3) = (c+1)log(5).

␈↓ ↓H␈↓This␈αis␈α
a␈αgeneralization␈α
of␈αthe␈α
earlier␈αresult␈α
that␈αminima␈α
occur␈αwhen␈α
(a+1)log(2)␈α=␈α(b+1)log(3).␈α
 We
␈↓ ↓H␈↓can easily see that the general pattern of the constraints are: (a␈↓#vi␈↓#+1)/(a␈↓#vj␈↓#+1) = log(p␈↓#vj␈↓#)/log(p␈↓#vi␈↓#),

␈↓ ↓H␈↓What␈α∞are␈α∂the␈α∞explicit␈α∂formulae␈α∞for␈α∂the␈α∞exponents␈α∂in␈α∞the␈α∂k=3␈α∞case?␈α∂ We␈α∞can␈α∂solve␈α∞for␈α∂them␈α∞in
␈↓ ↓H␈↓terms of d by using T1.  Namely,
␈↓ ↓H␈↓(a+1)(b+1)(c+1) = d
␈↓ ↓H␈↓(a+1) = (c+1)log(5)/log(2)
␈↓ ↓H␈↓(b+1) = (c+1)log(5)/log(3)

␈↓ ↓H␈↓Substituting␈α
the␈α
last␈α
two␈α
equations␈α
into␈α
the␈α
≡rst,␈α
we␈α
get␈α
(c+1)␈↓#
3␈↓#␈α
(log(5))␈↓#
2␈↓#␈α
=␈α
 d␈α
log(2)log(3).␈α Hence␈α
c+1
␈↓ ↓H␈↓= CUBEROOT[d log(2) log(3) / log␈↓#
2␈↓#(5)].

␈↓ ↓H␈↓For reasons which will become apparent soon, we will transform this slightly into

␈↓ ↓H␈↓c+1 = CUBEROOT[ d log(2) log(3) log(5) ] / log(5)

␈↓ ↓H␈↓The nicely symmetric equations for a+1 and b+1 turn out to be:
␈↓ ↓H␈↓a+1 = CUBEROOT[ d log(2) log(3) log(5) ] / log(2)
␈↓ ↓H␈↓b+1 = CUBEROOT[ d log(2) log(3) log(5) ] / log(3)

␈↓ ↓H␈↓Viewed␈α⊃in␈α⊃this␈α⊃way,␈α⊃we␈α∩can␈α⊃rewrite␈α⊃our␈α⊃equation␈α⊃from␈α⊃the␈α∩k=2␈α⊃case␈α⊃into␈α⊃the␈α⊃same␈α∩kind␈α⊃of
␈↓ ↓H␈↓expression, namely:
␈↓ ↓H␈↓a+1 = SQUAREROOT[ d log(2) log(3) ] / log(2)
␈↓ ↓H␈↓b+1 = SQUAREROOT[ d log(2) log(3) ] / log(3)

␈↓ ↓H␈↓Again the general pattern seems to be evident:
␈↓ ↓H␈↓a␈↓#vi␈↓#+1 = K␈↓#
t␈↓#␈↓#
h␈↓#ROOT[ d log(2) log(3)...log(p␈↓#vk␈↓#) ] / log(p␈↓#vi␈↓#)

␈↓ ↓H␈↓As␈αin␈αthe␈α
k=2␈αcase,␈αthe␈α
equations␈αfor␈αa,b,c␈α
have␈αreal␈αcorrespondence␈α
to␈αthe␈αoptimal␈αintegral␈α
values
␈↓ ↓H␈↓of the exponents.
␈↓ ↓H␈↓␈↓εDouglas B. Lenat␈↓␈↓ ∧s␈↓β␈↓&Automated Mathematician␈↓)αβ␈↓ results␈↓ λ9␈↓εMaximally-Divisible Numbers      page   4␈↓


␈↓ ↓H␈↓␈↓∧␈↓&General Case␈↓)αβ␈↓

␈↓ ↓H␈↓We␈αare␈αnow␈αready␈α
to␈αconsider␈αthe␈αmost␈α
general␈αcase,␈αnamely␈αwhen␈α
n␈α=␈α2␈↓#
a␈↓#␈↓#
␈↓ε␈↓#
1␈↓␈↓#
␈↓#3␈↓#
a␈↓#␈↓#
␈↓ε␈↓#
2␈↓␈↓#
...␈↓#p␈↓#vk␈↓#␈↓#
a␈↓#␈↓#
␈↓ε␈↓#
k␈↓␈↓#
␈↓#.␈α By␈α
T1,␈αwe
␈↓ ↓H␈↓know␈αthat␈αd(n)␈α=␈α(a␈↓#v1␈↓#+1)(a␈↓#v2␈↓#+1)...(a␈↓#v␈↓ε␈↓#vk␈↓␈↓#v␈↓#+1).␈α One␈αgeneralization␈αof␈αour␈αearlier␈αwork␈αwould␈αindicate␈αthat
␈↓ ↓H␈↓minima of n (for a given value of d) occur whenever

␈↓ ↓H␈↓␈↓∧(T2)␈↓ [for all i and j between 1 and k] (a␈↓#vi␈↓#+1)/(a␈↓#vj␈↓#+1) = log(p␈↓#vj␈↓#)/log(p␈↓#vi␈↓#).

␈↓ ↓H␈↓This␈αis␈αreally␈αa␈αset␈αof␈αk-1␈αequations␈αin␈αthe␈αk␈αdi≥erent␈αvariables␈αa␈↓#v1␈↓#,...,a␈↓#vk␈↓#.␈α Using␈αthe␈αformula␈αfor␈αd
␈↓ ↓H␈↓which␈α∞T1␈α∞provides,␈α∞we␈α∞can␈α∂solve␈α∞this␈α∞system␈α∞of␈α∞equations␈α∞for␈α∂each␈α∞a␈↓#vi␈↓#␈α∞in␈α∞terms␈α∞only␈α∞of␈α∂d.␈α∞The
␈↓ ↓H␈↓resulting formulae are:

␈↓ ↓H␈↓␈↓∧(T3)␈↓ [␈↓¬∀i≤k␈↓]  a␈↓#vi␈↓#+1 = K␈↓#
t␈↓#␈↓#
h␈↓#ROOT[ d log(2) log(3)...log(p␈↓#vk␈↓#) ] / log(p␈↓#vi␈↓#)

␈↓ ↓H␈↓The␈αproofs␈αof␈αT2␈αand␈αT3␈αare␈αleft␈αto␈αthe␈αreader.␈α␈↓ε(Hint:␈αI␈αcan␈αprove␈αone␈αof␈αthem␈αgiven␈αthe␈αother)␈↓.␈α Assuming
␈↓ ↓H␈↓them␈αas␈αtrue,␈αwe␈αcan␈αactually␈αcompute␈αthe␈αoptimal␈αvalues␈αfor␈αn.␈α It␈αwill␈αsimplify␈αmatters␈αagain␈αto
␈↓ ↓H␈↓consider␈α
only␈α
log(n)␈α
for␈αthe␈α
moment.␈α
 [note:␈α
SIGMA␈↓#vi␈↓#(...)␈αmeans␈α
"the␈α
sum,␈α
from␈αi=1␈α
to␈α
i=k,␈α
of␈α..."]
␈↓ ↓H␈↓Now
␈↓ ↓H␈↓log(n) = a␈↓#v1␈↓#log(2) + a␈↓#v2␈↓#log(3) +...+ a␈↓#vk␈↓#log(p␈↓#vk␈↓#)
␈↓ ↓H␈↓= SIGMA␈↓#vi␈↓#[log(p␈↓#vi␈↓#) a␈↓#vi␈↓#]
␈↓ ↓H␈↓= SIGMA␈↓#vi␈↓#[log(p␈↓#vi␈↓#)((K␈↓#
t␈↓#␈↓#
h␈↓#ROOT[ d log(2) log(3)...log(p␈↓#vk␈↓#) ]/log(p␈↓#vi␈↓#)) -  1)]
␈↓ ↓H␈↓= SIGMA␈↓#vi␈↓#[K␈↓#
t␈↓#␈↓#
h␈↓#ROOT( d log(2) log(3)...log(p␈↓#vk␈↓#) )  -  log(p␈↓#vi␈↓#)]
␈↓ ↓H␈↓= k[K␈↓#
t␈↓#␈↓#
h␈↓#ROOT( d log(2) log(3)...log(p␈↓#vk␈↓#))] -  SIGMA␈↓#vi␈↓#[log(p␈↓#vi␈↓#)]
␈↓ ↓H␈↓If we let F␈↓#vk␈↓# represent the product of the ≡rst k primes, then this says
␈↓ ↓H␈↓␈↓#vn␈↓# ␈↓#v=␈↓# ␈↓#ve␈↓#[k K␈↓#
t␈↓#␈↓#
h␈↓#ROOT(d) K␈↓#
t␈↓#␈↓#
h␈↓#ROOT(log(2)log(3)...log(p␈↓#vk␈↓#))]/F␈↓#vk␈↓#.
␈↓ ↓H␈↓If we let G␈↓#vk␈↓# be ␈↓#ve␈↓#[k K␈↓#
t␈↓#␈↓#
h␈↓#ROOT(log(2)...log(p␈↓#vk␈↓#))], then this becomes
␈↓ ↓H␈↓␈↓∧(T4)␈↓ ␈↓#vn␈↓# ␈↓#v=␈↓# ␈↓#vG␈↓#␈↓#v␈↓ε␈↓#vk␈↓␈↓#v␈↓#[K␈↓#
t␈↓#␈↓#
h␈↓#ROOT(d)]/F␈↓#vk␈↓#].

␈↓ ↓H␈↓So␈α
by␈α
tabulating␈α
G␈↓#vk␈↓#␈α∞and␈α
F␈↓#vk␈↓#,␈α
we␈α
can␈α∞e≠ciently␈α
compute␈α
the␈α
ideal␈α
value␈α∞for␈α
n␈α
(and␈α
for␈α∞each␈α
a␈↓#vi␈↓#)
␈↓ ↓H␈↓given␈α
a␈αdesired␈α
d␈α
and␈αallowable␈α
k.␈α
 Notice␈αthat␈α
if␈α
we␈αare␈α
allowed␈α
more␈αand␈α
more␈α
distinct␈αprime
␈↓ ↓H␈↓factors,␈αthat␈αis,␈αas␈αk␈αgrows,␈αthe␈αreal-valued␈αexponents␈αa␈↓#vi␈↓#␈αget␈αsmaller␈αand␈αsmaller,␈αuntil␈α≡nally␈αthey
␈↓ ↓H␈↓become␈α∂negative,␈α∞and␈α∂we␈α∂have␈α∞broken␈α∂all␈α∂ties␈α∞to␈α∂reality.␈α∂ Empirically,␈α∞the␈α∂ideal␈α∂value␈α∞obtained
␈↓ ↓H␈↓when␈α
no␈α
exponent␈α
is␈α
allowed␈α
to␈α
be␈α
below␈α
0.5␈α
is␈α
both␈α
close␈α
to,␈α
and␈α
slightly␈α
lower␈α
than,␈αany␈α
intergral
␈↓ ↓H␈↓solution.

␈↓ ↓H␈↓Of␈α
course␈α
this␈α
is␈α∞not␈α
satisfactory;␈α
what␈α
we␈α
now␈α∞need␈α
is␈α
a␈α
formula␈α
which␈α∞tells␈α
us,␈α
for␈α
a␈α∞given␈α
d,
␈↓ ↓H␈↓how␈αmany␈αdistinct␈αprime␈αfactors␈αany␈αn␈αmust␈αhave,␈αin␈αorder␈αto␈αhave␈αd␈αdivisors.␈αThat␈αis,␈αwe␈αwould
␈↓ ↓H␈↓like␈α
to␈α
know␈α
k␈α
as␈αa␈α
function␈α
of␈α
d.␈α
 As␈αit␈α
is,␈α
k␈α
increases␈α
like␈αlog(log(n)),␈α
hence␈α
is␈α
easy␈α
to␈αestimate
␈↓ ↓H␈↓empirically.
␈↓ ↓H␈↓␈↓εDouglas B. Lenat␈↓␈↓ ∧s␈↓β␈↓&Automated Mathematician␈↓)αβ␈↓ results␈↓ λ9␈↓εMaximally-Divisible Numbers      page   5␈↓


␈↓ ↓H␈↓␈↓∧␈↓&An even stronger claim␈↓)αβ␈↓

␈↓ ↓H␈↓There is another route out of this problem, namely if the following were true:

␈↓ ↓H␈↓␈↓∧(T5)␈↓␈α⊃The␈α⊃set␈α⊂M␈α⊃of␈α⊃maximally␈α⊃divisible␈α⊂numbers␈α⊃coincides␈α⊃precisely␈α⊂with␈α⊃the␈α⊃set␈α⊃of␈α⊂integers
␈↓ ↓H␈↓obtained in the following manner:
␈↓ ↓H␈↓␈↓ α_(1)␈αFor␈αeach␈αnatural␈αnumber␈αd,␈αuse␈αT3␈αto␈αcompute␈αthe␈αoptimal␈αexponents␈αfor␈αn(d,k),␈αwith␈αk
␈↓ ↓H␈↓␈↓ α_as large as possible such that no a␈↓#vi␈↓# is below 0.5
␈↓ ↓H␈↓␈↓ α_(2)␈α∞Round␈α∞each␈α∂exponent␈α∞to␈α∞the␈α∂nearest␈α∞integer,␈α∞and␈α∂compute␈α∞the␈α∞corresponding␈α∂n.␈α∞ Add
␈↓ ↓H␈↓␈↓ α_this n to the set.

␈↓ ↓H␈↓There␈α
is␈α
probably␈α
a␈α
nice␈α
closed-form␈α
formula␈αfor␈α
such␈α
numbers,␈α
a␈α
sort␈α
of␈α
"compiled"␈α
version␈αof
␈↓ ↓H␈↓T3␈α⊃and␈α⊃T5.␈α∩This␈α⊃is␈α⊃then␈α⊃the␈α∩desired␈α⊃characterization␈α⊃of␈α⊃M.␈α∩ Exhaustive␈α⊃search␈α⊃has␈α∩in␈α⊃fact
␈↓ ↓H␈↓con≡rmed␈αT5␈αfor␈α
all␈αd␈αbelow␈α
1500.␈α T5␈αhas␈α
the␈αadvantage␈αof␈α
being␈αintuitively␈αclear.␈α
Perhaps␈αits
␈↓ ↓H␈↓proof␈αwill␈αturn␈αout␈αto␈αbe␈αnontrivial␈αor␈αnonexistent.␈αI␈αleave␈αit␈αas␈α"AM's␈αconjecture".␈α This␈αis␈αso␈αfar
␈↓ ↓H␈↓the␈α
only␈α
piece␈αof␈α
interesting␈α
mathematics,␈αpreviously␈α
unknown,␈α
that␈αwas␈α
directly␈α
motivated␈αby␈α
AM
␈↓ ↓H␈↓(a␈α
computer␈αprogram,␈α
written␈αby␈α
Lenat,␈α
which␈αproposes␈α
new␈αand␈α
supposedly␈α
interesting␈αconcepts
␈↓ ↓H␈↓to investigate).

␈↓ ↓H␈↓For␈α
example:␈α
consider␈αd=1344.␈α
The␈α
largest␈αthat␈α
k␈α
can␈αbe␈α
without␈α
T3␈αcalling␈α
for␈α
␈↓¬a␈↓#vk␈↓#␈α<␈α
0.5␈↓␈α
is␈αk=7.
␈↓ ↓H␈↓For␈αthis␈αd␈αand␈αk,␈αT3␈α
predicts␈αexponents␈α5.9,␈α3.3,␈α2.0,␈α1.4,␈α
1.0,␈α0.9,␈αand␈α0.7.␈α Rounding␈αthis␈α
o≥,␈αwe
␈↓ ↓H␈↓get␈α
6,␈α
3,␈α
2,␈α
1,␈α
1,␈α1,␈α
1.␈α
Next␈α
we␈α
compute␈α
2␈↓#
6␈↓#3␈↓#
3␈↓#5␈↓#
2␈↓#7␈↓#
1␈↓#11␈↓#
1␈↓#13␈↓#
1␈↓#17␈↓#
1␈↓#.␈αThis␈α
is␈α
735,134,400.␈α
T1␈α
tells␈α
us␈αthat
␈↓ ↓H␈↓this␈αhas␈αin␈αfact␈αprecisely␈α1344␈αdivisors␈α(coincidence).␈αExhaustive␈αsearch␈αtells␈αus␈αthat␈αno␈α
smaller␈αn
␈↓ ↓H␈↓has␈αthat␈αmany␈αdivisors␈α(this␈αis␈αa␈αveri≡cation␈αof␈αT5).␈α Incidentally,␈αthe␈αideal␈αvalue␈αfor␈αn␈α(for␈αthis␈αk
␈↓ ↓H␈↓and␈αd␈αvalue)␈αis␈α603,696,064.␈α Notice␈αthat␈αit␈αis␈αclose␈αto,␈αand␈αless␈αthan,␈αthe␈αbest␈αpossible␈αn␈αwith␈α1344
␈↓ ↓H␈↓divisors.

␈↓ ↓H␈↓Another␈α∞such␈α∞"rounded-exponent"␈α∞number␈α∞is␈α∞n=2␈↓π8␈↓3␈↓π5␈↓5␈↓π3␈↓7␈↓π2␈↓11␈↓π2␈↓13␈↓π1␈↓17␈↓π1␈↓19␈↓π1␈↓23␈↓π1␈↓29␈↓π1␈↓31␈↓π1␈↓37␈↓π1␈↓41␈↓π1␈↓43␈↓π1␈↓47␈↓π1␈↓53␈↓π1␈↓.
␈↓ ↓H␈↓The␈α
progression␈α
of␈α
its␈αexponents+1␈α
(9␈α
6␈α
4␈α3␈α
3␈α
2␈α
2␈α
2␈α2␈α
2␈α
2␈α
2␈α2␈α
2␈α
2␈α
2)␈α
is␈α about␈α
as␈α
 close␈α
 as␈αone␈α
 can
␈↓ ↓H␈↓get␈α to␈αsatisfying␈αthe␈α "logarithm"␈αconstraint.␈α By␈αthat␈αI␈αmean␈αthat␈α9/6␈αis␈αclose␈αto␈αlog(3)/log(2);␈αthat
␈↓ ↓H␈↓2/2␈αis␈αclose␈αto␈αlog(47)/log(43),␈αetc.␈α Changing␈αany␈αexponent␈αby␈αplus␈αor␈αminus␈α1␈αwould␈αmake␈αthose
␈↓ ↓H␈↓ratios␈αworse␈αthan␈αthey␈αare.␈α This␈α number␈αn␈αis␈αabout␈α25␈αbillion,␈αand␈αhas␈αabout␈α4␈αmillion␈αdivisors.
␈↓ ↓H␈↓The␈αAM␈αconjecture␈αis␈αthat␈αthere␈αis␈αno␈αsmaller␈αnumber␈αwith␈αthat␈αmany␈αdivisors.␈α Incidentally,␈αthe
␈↓ ↓H␈↓average number in the neighborhood of n has about 2␈↓#
loglog n␈↓# divisors (about 9, for this n).
␈↓ ↓H␈↓␈↓εDouglas B. Lenat␈↓␈↓ ∧s␈↓β␈↓&Automated Mathematician␈↓)αβ␈↓ results␈↓ λ9␈↓εMaximally-Divisible Numbers      page   6␈↓


␈↓ ↓H␈↓␈↓∧␈↓&New Questions and Tasks␈↓)αβ␈↓

␈↓ ↓H␈↓Supply proof of T1 (see standard Number Theory text if stuck).

␈↓ ↓H␈↓Supply proof that the "ideal" exponents have real signi≡cance for the special case of k=2.

␈↓ ↓H␈↓Supply proof of this fact for k=3 or general case.

␈↓ ↓H␈↓Supply proof of T2 (di≠cult).

␈↓ ↓H␈↓Supply proof of T3 (messy but not too hard, given T2).

␈↓ ↓H␈↓Tabulate the constants G␈↓#vk␈↓# and F␈↓#vk␈↓# (as used in T4), and notice new regularities.

␈↓ ↓H␈↓Find␈α
k(d).␈α
That␈α
is,␈αgiven␈α
a␈α
desired␈α
number␈αof␈α
divisors␈α
d,␈α
how␈αmany␈α
distinct␈α
prime␈α
divisors␈αwill␈α
be
␈↓ ↓H␈↓possessed by the smallest number with d divisors.

␈↓ ↓H␈↓Prove T5. Or, establish it empirically for large d. Or, prove it for special cases.

␈↓ ↓H␈↓Devise␈αa␈αcalculus␈αof␈αthese␈αmaximally-divisible␈αnumbers.␈α What␈αabout␈αtheir␈αproduct?␈αsum?␈α
 If␈αthe
␈↓ ↓H␈↓quotient of two members of M is divisible by 2, then there is a high probability that it is in M.

␈↓ ↓H␈↓Empirically,␈α␈↓¬if␈α
xεM,␈αthen␈α
there␈αis␈α
a␈αhigh␈αprobability␈α
that␈αd(x)εM.␈↓␈α
Why?␈αWhat␈α
is␈αthe␈α
signi≡cance␈αof
␈↓ ↓H␈↓this? Can you use it to ≡nd new, large members of M?

␈↓ ↓H␈↓Can␈αM␈α
be␈αused␈αto␈α
shorten␈αproofs␈αabout␈α
the␈αnormal␈αorder␈α
of␈αd(n)?␈α Can␈α
many␈αdeep␈αconjectures␈α
be
␈↓ ↓H␈↓posed␈αcheaply␈α(as␈α
with␈αprimes)␈αby␈α
asking␈αabout␈αrelations␈αinvolving␈α
addition␈αand␈αM?␈α
 (e.g.,␈αevery
␈↓ ↓H␈↓number x is the sum of at most log(x) members of M)

␈↓ ↓H␈↓Can␈αmembers␈αof␈αM␈αbe␈αused␈αto␈αspeed␈αup␈αfactoring␈αalgorithms?␈α How␈αabout␈αusing␈αM␈αto␈α≡nd␈αlarge
␈↓ ↓H␈↓primes? Prime pairs? What is the neighborhood of members of M like?